\documentclass[10pt,english,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{babel,graphicx}
\usepackage{fancybox} 
\usepackage{graphicx}


\usepackage{times}
\usepackage{url}

\usepackage{float}
 
\floatstyle{ruled}
\newfloat{program}{thb}{lop}
\floatname{program}{Code example}


\bibliographystyle{holeproof}

\title{Compulsory 2 - INF210}
\author{Tobias Rusås Olsen -tol060@student.uib.no\\Fall 2008}
\date{\today}

\tolerance = 5000

\hbadness = \tolerance 
\pretolerance = 2000
% mange lange sammensatte ord.


\begin{document}

\begin{titlepage}
\maketitle
\thispagestyle{empty}


\end{titlepage}

\pagenumbering{arabic}

\newpage


\section{Problem 1}

Problem 4.14 in Savage.

\subsection{a}

\includegraphics[width=.7\textwidth]{nfsm.jpg}

Description: If the length of input is 1, it will go to a final state f. If not,
it will enter the appropiate ``loop'', and exit to the final state if the
correct input is given. If anything more is read from the final state f, we will
enter the halting state h.


\subsection{b}

We start by finding the set of states possible to reach from the start-state,
on all possible input (0,1,2).Then we do the same for each possible set of
states that are outcomes from the startstate. For each new combination of
states, we must add it's possible outcomes. We end up with a long list of
possible transactions for each set of states. For each new state, we appoint a
new letter. After we have inputted all the neccesary data, we can fill the ``To
state''-letter, according to the letter given to the set of states connected to
that letter.

\begin{tabular}{|c|c|c|c|c|}
\hline $q_{equiv}$ & a & $M_{equiv}$ ($q_{equiv}$,a) & Appointed letter & To
state\\
\hline
\hline \{s\} & 0 & \{a,b,f\} & a & b \\
\hline \{s\} & 1 & \{a,c,f\} & a & c \\
\hline \{s\} & 2 & \{b,c,f\} & a & d \\
\hline
\hline \{a,b,f\} & 0 & \{a,b,h\} & b & e \\
\hline \{a,b,f\} & 1 & \{a,f,h\} & b & f \\
\hline \{a,b,f\} & 2 & \{b,f,h\} & b & g \\
\hline
\hline \{a,c,f\} & 0 & \{a,f,h\} & c & f \\
\hline \{a,c,f\} & 1 & \{a,c,h\} & c & h \\
\hline \{a,c,f\} & 2 & \{c,f,h\} & c & i \\
\hline
\hline \{b,c,f\} & 0 & \{b,f,h\} & d & g \\
\hline \{b,c,f\} & 1 & \{c,f,h\} & d & i \\
\hline \{b,c,f\} & 2 & \{b,c,h\} & d & j \\
\hline
\hline \{a,b,h\} & 0 & \{a,b,h\} & e & e \\
\hline \{a,b,h\} & 1 & \{a,f,h\} & e & f \\
\hline \{a,b,h\} & 2 & \{b,f,h\} & e & g \\
\hline
\hline \{a,f,h\} & 0 & \{a,h\} & f & k \\
\hline \{a,f,h\} & 1 & \{a,h\} & f & k \\
\hline \{a,f,h\} & 2 & \{f,h\} & f & l \\
\hline
\hline \{b,f,h\} & 0 & \{b,h\} & g & m \\
\hline \{b,f,h\} & 1 & \{f,h\} & g & l \\
\hline \{b,f,h\} & 2 & \{b,h\} & g & m \\
\hline
\hline \{a,c,h\} & 0 & \{a,f,h\} & h & f \\
\hline \{a,c,h\} & 1 & \{a,c,h\} & h & h \\
\hline \{a,c,h\} & 2 & \{c,f,h\} & h & i \\
\hline
\hline \{c,f,h\} & 0 & \{f,h\} & i & l \\
\hline \{c,f,h\} & 1 & \{c,h\} & i & n \\
\hline \{c,f,h\} & 2 & \{c,h\} & i & n \\
\hline
\hline \{b,c,h\} & 0 & \{b,f,h\} & j & g \\
\hline \{b,c,h\} & 1 & \{c,f,h\} & j & i \\
\hline \{b,c,h\} & 2 & \{b,c,h\} & j & j \\
\hline
\hline \{a,h\} & 0 & \{a,h\} & k & k \\
\hline \{a,h\} & 1 & \{a,h\} & k & k \\
\hline \{a,h\} & 2 & \{f,h\} & k & l \\
\hline
\hline \{f,h\} & 0 & \{h\} & l & o \\
\hline \{f,h\} & 1 & \{h\} & l & o \\
\hline \{f,h\} & 2 & \{h\} & l & o \\
\hline
\hline \{b,h\} & 0 & \{b,h\} & m & m \\
\hline \{b,h\} & 1 & \{f,h\} & m & l \\
\hline \{b,h\} & 2 & \{b,h\} & m & m \\
\hline
\hline \{c,h\} & 0 & \{f,h\} & n & l \\
\hline \{c,h\} & 1 & \{c,h\} & n & n \\
\hline \{c,h\} & 2 & \{c,h\} & n & n \\
\hline
\hline \{h\} & 0 & \{h\} & o & o \\
\hline \{h\} & 1 & \{h\} & o & o \\
\hline \{h\} & 2 & \{h\} & o & o \\
\hline
\end{tabular}
\\
\\
The final states are the set of states including the final state f. In this
problem, the final states are: b,c,d,f,g,i and l.

By following these instructions, we can create a deterministic finite state
machine, looking somewhat like this:

\includegraphics[width=.9\textwidth]{dfsm.jpg}

\newpage

\section{Problem 2}

\subsection{a}

We have two final states q1 and q4, the solution is the start-state to one of
the final states plus the start-state to the other final state:\\
$r^{(5)}_{1,1}$ + $r^{(5)}_{1,5}$

\subsection{b}
For expressing this with $r^{(4)}_{i,j}$, we must use the following lemma:\\  
$r^{(k)}_{i,j}$ = $r^{(k-1)}_{i,j}$ + $r^{(k-1)}_{i,k}$
$(r^{(k-1)}_{k,k})^{*}$ $r^{(k-1)}_{k,j}$
\\
\\
We have two values for i and j: 1,1 and 1,4:\\
$r^{(5)}_{1,1}$ = $r^{(4)}_{1,1}$ + $r^{(4)}_{1,5}$
$(r^{(4)}_{5,5})^{*}$ $r^{(4)}_{5,1}$
\\
$r^{(5)}_{1,4}$ = $r^{(4)}_{1,4}$ + $r^{(4)}_{1,5}$
$(r^{(4)}_{5,5})^{*}$ $r^{(4)}_{5,4}$
\\
\\
From this, we see that we need the following:\\
\\
$r^{(4)}_{1,1}$\\
\\
$r^{(4)}_{1,4}$\\
\\
$r^{(4)}_{1,5}$\\
\\
$r^{(4)}_{5,4}$\\
\\
$r^{(4)}_{5,5}$\\

\subsection{c}

The table $T^{(4)}$ / $r^{(4)}_{i,j}$:

\begin{tabular}{|c|c|c|c|c|c|}
\hline - & 1 & 2 & 3 & 4 & 5 \\
\hline 1 & $\varepsilon$+$(00)^{*}$ & 0$(00)^{*}$ & 1$(11)^{*}$ & 11$(11)^{*}$
& 01+11+110+1110 \\ 
\hline 2 & 0$(00)^{*}$ & $\varepsilon$ + $(00)^{*}$ & 01$(11)^{*}$ & 011 &
1+010+0110\\ 
\hline 3 & $\phi$ & $\phi$ & $\varepsilon$+$(11)^{*}$ & 1$(11)^{*}$ & 0+10 \\
\hline 4 & $\phi$ & $\phi$ & 1$(11)^{*}$ & $\varepsilon$+$(11)^{*}$ & 0+10 \\
\hline 5 & $\phi$ & $\phi$ & $\phi$ & $\phi$ & $\varepsilon$+$(0+1)^{*}$\\
\hline   

\end{tabular}
\\
The equation expressed by $r^{(4)}_{i,j}$:\\ 
\\
$r^{(4)}_{1,1}$ + $r^{(4)}_{1,5}$ $(r^{(4)}_{5,5})^{*}$ $r^{(4)}_{5,1}$ +
$r^{(4)}_{1,4}$ + $r^{(4)}_{1,5}$ $(r^{(4)}_{5,5})^{*}$ $r^{(4)}_{4,1}$
\\
\\
We look in the table, and fill in the spots:\\
\\
$r^{(5)}_{1,1}$ = ($\varepsilon$+$(00)^{*}$) +
(01+11+110+1110) $(\varepsilon+ (1+0)^{*})^{*})$ $\phi$\\
\\
$r^{(5)}_{1,4}$ = (11$(11)^{*}$) +
(01+11+110+1110) $(\varepsilon+ (1+0)^{*})^{*})$ $\phi$\\
\\
This is our long regular expression:\\
($\varepsilon$+$(00)^{*}$) + (01+11+110+1110) $(\varepsilon+ (1+0)^{*})^{*})$
$\phi$ + (11$(11)^{*}$) + (01+11+110+1110) $(\varepsilon+ (1+0)^{*})^{*})$ $\phi$

\subsection{d}
Lets use rule 1 on both : r$\phi$ = $\phi$r = $\phi$ the two places where
$\phi$ occurs. This removes alot.\\

r = ($\varepsilon$+$(00)^{*}$) + (11$(11)^{*}$)\\

Now we can use rule 12: $(\varepsilon + r)^{*})$ = $r^{*}$ to remove
the $\varepsilon$\\ (in combination with rule 3).

r = $(00)^{*}+$11$(11)^{*}$

\newpage

\section{Problem 3}

The strengthened pumping lemma shows that if you have a word w of the
length $\geq$ m (number of states in fsm), than you have also have a substring
with length exactly m, where you can apply the pumping lemma. This is a more presice
definition of the pumping lemma, as it can find the exact substring where the
pumping can be done. If we consider the fsm that is related to the regular
language, this means that we can find the path where the repitition occurs.
This means that we can exclude the $\mid$rs$\mid$ $\leq$ m from the lemma,
since it's already covered by the fact that the substring has length m.

\section{Problem 4}

Let's choose the word w = $a^{p}b^{p-1}$\\
\\
w = uzv\\
\\
z = rst\\
\\
$\mid$s$\mid$ $\geq$ 1\\
\\
s = $a^{n}$\\
\\
Lets say that n is 0. Then we have:\\
\\
w = urtv\\
\\
This means that we have removed at least one a. This means that there are
either less a's than b's, or that they are equal. This obviously violates the
rules of the language, hence it's not regular.

\section{Problem 5}

\includegraphics[width=.7\textwidth]{433-pda.jpg}

Description: You start in the state s. If you read 0 from s, you add 0 to the
stack. If you read 1, you either remove a 0 from the stack, or if the stack is empty: Go to state f. 

If you read 1 from state f, you add 1 to the stack. If you read 0, you either
remove a 1 from the stack, of if the stack is empty: Go to state s. f is a final
state.

\newpage

\section{Problem 6}

We follow the rules in chapter 4.10:

\begin{itemize}
  \item Start symbol is the start state of m.
  \item Create a new rule q1 $\rightarrow$ aq2 if the dfsm makes a transition
  from q1 to q2 on input a.
  \item If state q is a final state, add the rule q $\rightarrow$ $\varepsilon$  
\end{itemize}

By following these guidelines, we create have the following rules: 
\\
S $\rightarrow$ q$_{0}$\\
q$_{0}$ $\rightarrow$ 0q$_{2}$ \\
q$_{0}$ $\rightarrow$ 1q$_{1}$\\ 
q$_{1}$ $\rightarrow$ 0q$_{3}$ \\
q$_{1}$ $\rightarrow$ 1q$_{0}$ \\
q$_{2}$ $\rightarrow$ 0q$_{0}$ \\
q$_{2}$ $\rightarrow$ 1q$_{3}$ \\
q$_{3}$ $\rightarrow$ 0q$_{1}$ \\
q$_{3}$ $\rightarrow$ 1q$_{2}$ \\
q$_{2}$ $\rightarrow$ $\varepsilon$\\
\\
Let try parsing 01010:\\
\\
S $\rightarrow$ q$_{0}$ $\rightarrow$ 0q$_{2}$ $\rightarrow$ 01q$_{3}$ $\rightarrow$
010q$_{1}$ $\rightarrow$ 0101q$_{0}$ $\rightarrow$ 01010q$_{2}$ $\rightarrow$
01010. We made it!
\\
Now let's try parsing 0101:\\ 
\\
S $\rightarrow$ q$_{0}$ $\rightarrow$ 0q$_{2}$ $\rightarrow$ 01q$_{3}$ $\rightarrow$
010q$_{1}$ $\rightarrow$ 0101q$_{0}$.
\\ 
Since there is no q$_{0}$ $\rightarrow$ $\varepsilon$, we can't remove the
Non-terminal q$_{0}$ without reading further input, in hope of reaching the
final state.

\newpage

\section{Problem 7}

\subsection{a}
To show that the grammar is is context-sensitive, we must show two things: 

\begin{itemize}
  \item 1: It falls under the definition of context-sensitive grammars.
  \item 2: It is not a context-free grammar. 
\end{itemize}

Is falls under the first one because it follows the following rule: Each rule
(a,b) R satisfies $\mid$a$\mid$ $\leq$ $\mid$b$\mid$. That means that the
left-hand side of the rules cannot have more symbols than the right-hand side. 
\\
\\
Now we must prove that it is not a context-free grammar. This
is trivial, because you have rules of the production BA $\rightarrow$ AB and bB
$\rightarrow$ bb, which both violate the rule for context-free languages by not having a single
non-terminal on the left-hand side.

\subsection{b}

L(G) = \{ $a^{n}$ $b^{n}$ $c^{n}$ $\mid$ n $\geq$ 1 \} 
\\
Explanation: First we make one or more ABC ($ABC^{+}$) by using the rules with S
og S1 on the left hand side. Now the only way to end up with terminals, is by
using the rules BA $\rightarrow$ AB, CA $\rightarrow$ AC and CB $\rightarrow$
BC to get A before B, and B before C.
\\
Therefore we will always end up with the same amount of the terminals a,b and
c, in that order. n must be bigger or equal to 1 because we don't have
productions from S $\rightarrow$ $\varepsilon$

\subsection{c}
We will prove this by using the pumping lemma for context-free grammars.

We assume L is a context-free grammer, and show that it contains strings
outside of L.\\
\\
m is the number of non-terminals.
$n_{0}$ = $2^{m-1}$+1.\\
\\
L is infinite, therefore we can use the pumping lemma.\\
\\
rstuv = $a^{n}$ $b^{n}$ $c^{n}$ for n = $n_{0}$.\\
\\
From the pumping lemma, we can say that r$s^{2}$t$u^{2}$v should also be in L.
As long as s or u is not empty, they contain one, two or three symbols from the
alphabet $\Sigma$. If they have more than one symbol, it will break the
ordering (by having b before a and similar), this mean that they can only have
one symbol, but this contradicts the fact that the number of a,b and c's
in r$s^{2}$t$u^{2}$v are not the same (two or three will be bigger then the
last one).

\end{document}